package com.base.dynamicprograming;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 740. 删除并获得点数
 * <p>
 * 给你一个整数数组nums，你可以对它进行一些操作。
 * <p>
 * 每次操作中，选择任意一个nums[i]，删除它并获得nums[i]的点数。之后，你必须删除 所有 等于nums[i] - 1 和 nums[i] + 1的元素。
 * <p>
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-and-earn
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年11月23日 20:08
 */
public class DeleteAndEarn {

    public int deleteAndEarn(int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i],0)+nums[i]);
        }
        int[] keys = new int[map.size()];
        int k = 0;
        for (Integer j :map.keySet()){
            keys[k++] = j;
        }
        int[] dp = new int[map.size() + 1];
        dp[1] = map.get(keys[0]);
        for (int i = 1; i < keys.length; i++) {
            if (keys[i] - keys[i - 1] == 1) {
                dp[i + 1] = Math.max(dp[i - 1] + map.get(keys[i]), dp[i]);


            } else {
                dp[i + 1] = dp[i] + map.get(keys[i]);
            }
        }
        return dp[dp.length-1];

    }

    /**  官方题解1 用一个所有元素的最大的数组作为hash表，按照打家截舍处理
     * 作者：LeetCode-Solution
     *     链接：https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/
     *     来源：力扣（LeetCode）
     *     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public int deleteAndEarn1(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
    /**
    注意到若 \textit{nums}nums 中不存在某个元素 xx，则选择任一小于 xx 的元素不会影响到大于 xx 的元素的选择。因此我们可以将 \textit{nums}nums 排序后，
    将其划分成若干连续子数组，子数组内任意相邻元素之差不超过 11。对每个子数组按照方法一的动态规划过程计算出结果，累加所有结果即为答案。

    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int deleteAndEarn2(int[] nums) {
        int n = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        List<Integer> sum = new ArrayList<Integer>();
        sum.add(nums[0]);
        int size = 1;
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.set(size - 1, sum.get(size - 1) + val);
            } else if (val == nums[i - 1] + 1) {
                sum.add(val);
                ++size;
            } else {
                ans += rob(sum);
                sum.clear();
                sum.add(val);
                size = 1;
            }
        }
        ans += rob(sum);
        return ans;
    }

    public int rob(List<Integer> nums) {
        int size = nums.size();
        if (size == 1) {
            return nums.get(0);
        }
        int first = nums.get(0), second = Math.max(nums.get(0), nums.get(1));
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums.get(i), second);
            first = temp;
        }
        return second;
    }



    public static void main(String[] args) {
        new DeleteAndEarn().deleteAndEarn(new int[]{2, 2, 2, 3, 3, 4, 4});

    }
}
